package sorter;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class test {
    List<List<Integer>> res;
    boolean []used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        res = new ArrayList<>();
        if(nums.length == 0) return res;
        Arrays.sort(nums);
        used = new boolean[nums.length+1];
        pre(nums, 0, new LinkedList<>());
        return res;
    }
    public void pre(int []nums, int index,
                    LinkedList<Integer> list){
        System.out.println("index:"+index);
        if(index == nums.length) {
            res.add(new LinkedList<>(list));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            System.out.println("nums = "+nums[i]);
            if(used[i] ||
                    (i > 0 && nums[i] == nums[i-1] && !used[i-1])){
                System.out.println("没添加："+nums[i]);
                continue;
            }
            used[i]=true;
            list.addLast(nums[i]);
            System.out.println("添加了："+nums[i]);
            pre(nums, index+1, list);
            used[i]=false;
            list.removeLast();
        }

    }

    public static void main(String[] args) {
        test test = new test();
        int []nums = {1,1,2};
        List<List<Integer>> lists = test.permuteUnique(nums);
        System.out.println(lists);
    }
}